package com.company.动态规划;

public class Leet198 {
    private int[] nums;
    /*
     * 直接递归
     * >=i区间内 偷出的最大金额
     */
    private int dp1(int i){
        if(i == nums.length-1){
            return nums[i];
        }
        if(i == nums.length-2){
            return Math.max(nums[i], nums[i+1]);
        }
        //(不偷，偷)
        return Math.max(dp1(i+1), dp1(i+2)+nums[i]);
    }

    /**
     * 记忆化搜索
     */
    private Integer[] ans;
    private int dp2(int i){
        if(i == nums.length-1){
            return nums[i];
        }
        if(i == nums.length-2){
            return Math.max(nums[i], nums[i+1]);
        }
        //搜索记录
        if(ans[i] != null){
            return ans[i];
        }
        int res = Math.max(dp2(i+1), dp2(i+2)+nums[i]);
        //记录
        ans[i] = res;
        return res;
    }
    public int rob(int[] nums) {
        this.nums = nums;
        this.ans=new Integer[nums.length];
        return dp2(0);
    }
}
